import java.util.Stack;

public class OptimumCode {
    /**
     * 我们有一个表存了m个文本串,每个长度至多为k。我们想对一个长为n的数据串D使用尽可能少的文本串来编码。
     * 输入：codes = ["a","ba","abab","b"] str = "bababbaababa"
     * 输出：5
     * 解释：编码的最好方式是(“b”，“abab”, “ba” ,“abab”,“a”)
     * 给出一个O(nmk)算法找出最优编码的码长。你可以假设每个文本串都可以基于该表至少给出一个编码。
     */

    /**
     * 1. 定义状态：设dp[i]表示的是字符串前i个字符组成的字符串最优码长，我们要求的是dp[str.length]即为字符的最优码长
     * 2. 定义状态转移方程：当k <= j并且字符串后k个字符组成字符串与编码匹配时, k为编码集中编码长度组成的集合
     * dp[i]=min(dp[i-k]+1);
     * 3. 初始化：dp[1]=1;
     * 4. 计算方式：从左到右
     */

    /**
     *
     * @param codes
     * @param str
     * @param trace
     * @return
     */

    /**
     * 最优编码数量
     *
     *  @author hh
     *  @date 2021-5-20 21:48
     */

        public int optimumCode(String[] codes,String str,String[] trace){
            int[] dp = new int[str.length() + 1];
            //初始化dp[1] = 1
            dp[1] = 1;
            for(int i = 1; i <= str.length(); i++){
                dp[i] = Integer.MAX_VALUE;
                for(String bizCode : codes){
                    if(bizCode.length() > i){
                        continue;
                    }
                    int temp = dp[i - bizCode.length()] + 1;
                    if(str.substring(i - bizCode.length(),i).equals(bizCode) && dp[i] > temp){
                        dp[i] = temp;
                        trace[i] = bizCode;
                    }
                }
            }
            return dp[str.length()];
        }

        public void print(String[] trace,int index){
            Stack<String> stringStack = new Stack<>();
            while (index >= 1){
                stringStack.push(trace[index]);
                index -= trace[index].length();
            }
            System.out.print("最优编码为：");
            while (!stringStack.isEmpty()){
                if(stringStack.size() == 1){
                    System.out.print(stringStack.pop());
                }else{
                    System.out.print(stringStack.pop() + ",");
                }
            }
        }

        public static void main(String[] args){
            String[] codes = new String[]{"a","ba","abab","b"};
            String str = "bababbaababa";
            String[] trace = new String[str.length() + 1];
            OptimumCode optimumCode = new OptimumCode();
            System.out.println("最优编码长度：" +  optimumCode.optimumCode(codes,str,trace));
            optimumCode.print(trace,str.length());
        }
}
